//
// Created by liushuai on 2021/2/3.
//

#include "addInList.h"
ListNode* addInList(ListNode* head1, ListNode* head2) {
  stack<ListNode*> stack1;
  stack<ListNode*> stack2;
  if (!head1) return head2;
  if (!head2) return head1;
  while (head1) {
    stack1.push(head1);
    head1 = head1->next;
  }
  while (head2) {
    stack2.push(head2);
    head2 = head2->next;
  }
  int min_stack = stack1.size() < stack2.size() ? stack1.size() : stack2.size();
  int forward = 0;
  deque<int> res;

  for (int i = 0; i < min_stack; i++) {
    int value = stack2.top()->val + stack1.top()->val + forward;
    forward = value / 10;
    res.push_back(value % 10);
    stack1.pop();
    stack2.pop();
  }
  while (!stack1.empty()) {
    int value = stack1.top()->val + forward;
    forward = value / 10;
    stack1.pop();
    res.push_back(value % 10);
  }
  while (!stack2.empty()) {
    int value = stack2.top()->val + forward;
    forward = value / 10;
    stack2.pop();
    res.push_back(value % 10);
  }
  if (forward) res.push_back(forward);
  ListNode* head = nullptr;
  ListNode* temp = head;
  while (!res.empty()) {
    ListNode* current = new ListNode(res.back());
    if (!temp) {
      head = current;
      temp = head;
      res.pop_back();
    } else {
      temp->next = current;
      temp = current;
      res.pop_back();
    }
  }
  return head;
}